package linear;

import node.node;

public class linear implements linearinterface {
    // object数组
    // 头结点
    node head = new node();
    int length = 0;

    @Override
    public void add(node node) {
        // 头插法
        node.next = this.head.next;
        head.next = node;
        length++;
    }

    // 直接插入
    @Override
    public void sortById() {
        // 存储当前趟的操作位置(操作结点为p.next)
        node p = this.head.next;
        // 循环遍历直到操作完成
        while (p != null) {
            // 用于矛定比较位置,根据插入排序定义可以确定其位置区间为头结点到操作位置
            node frunner = this.head;
            // 防止结点传染,保存下一趟p应该在的位置
            node next = p.next;
            // 插入操作事件循环
            while (frunner.next != p.next && p.next != null) {
                // 确定操作结点的插入位置,找到后进行插入操作
                if (p.getIndex(true) < frunner.next.getIndex(true)) {
                    // 存储操作结点
                    node tmp = p.next;
                    // 操作结点删除
                    p.next = p.next.next;
                    // 操作结点next指针继承待插入位置的next指针
                    tmp.next = frunner.next;
                    // 结点插入
                    frunner.next = tmp;
                    // 执行完毕后跳出事件循环
                    break;
                }
                frunner = frunner.next;
            }
            // p位置调整
            p = next;
        }
    }

    @Override
    public void print() {
        node p = head.next;
        while (p != null) {
            System.out.println(p);
            p = p.next;
        }
    }

    // 根据ID改名字
    @Override
    public void update(int id, String name, int age) {
        node p = head.next;
        while (p != null) {
            if (p.id == id) {
                p.name = name;
                break;
            }
            p = p.next;
        }
        // 修改name
        p.name = name;
        // 修改age
        p.age = age;
    }

    @Override
    public void delete(int id) {
        node p = head;
        while (p.next != null) {
            if (p.next.id == id) {
                p.next = p.next.next;
                break;
            }

            p = p.next;
        }
        p.next = p.next.next;
        length--;
    }

    @Override
    public node find(int index) {
        // 链表转换成数组
        node[] nodeArray = new node[this.length()];
        // 二分
        int left = 0;
        int right = this.length() - 1;
        int mid = (left + right) / 2;
        int i = 0;
        node p = head.next;
        while (p != null) {
            nodeArray[i] = p;
            p = p.next;
            i++;
        }
        // 二分查找
        while (left <= right) {
            if (nodeArray[mid].id == index) {
                return nodeArray[mid];
            } else if (nodeArray[mid].id > index) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        }
        return null;
    }

    // 按照名字查找
    @Override
    public node find(String name) {
        node p = head.next;
        while (p != null) {
            if (p.name.equals(name)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    @Override
    public int length() {
        return this.length;
    }

    // 简单选择排序
    @Override
    public void sortByAge() {
        // 存储剩余的待排序的结点(或理解为将当前链表中的元素交给ready)
        node ready = this.head;
        // 存储已排序结点并将已排序结点串交给list
        node sorted = new node();
        this.head = sorted;
        // 循环遍历剩余结点直到剩余结点为空
        while (ready.next != null) {
            // 用于在剩余结点中游离
            node prepared = ready;
            // 寻找最小结点(最小结点的位置是min.next)
            node min = prepared;
            while (prepared.next != null) {
                if (prepared.next.getIndex(false) < min.next.getIndex(false)) {
                    min = prepared;
                }
                prepared = prepared.next;
            }
            // 在已排序序列中添加当前趟最小值
            sorted.next = min.next;
            // 删除此趟最小值
            min.next = min.next.next;
            // 重新矛定已排序的末尾位置
            sorted = sorted.next;
        }
    }
}
